package dp.beibao;

import java.util.Arrays;

/**
 * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
 *
 * 题目数据保证答案符合 32 位整数范围。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3], target = 4
 * 输出：7
 * 解释：
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。
 * 示例 2：
 *
 * 输入：nums = [9], target = 3
 * 输出：0
 */
public class leetCode377_CombinationSum4 {
    /**
     * dp[i]: 凑成目标正整数为i的组合个数为dp[i]
     * 可以取出多次，所以是完全背包问题
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum(int[] nums, int target) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if(i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
     }

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        int target = 4;
        leetCode377_CombinationSum4 leetCode377_combinationSum4 = new leetCode377_CombinationSum4();
        int i = leetCode377_combinationSum4.combinationSum(nums, target);
        System.out.println(1);
    }
}
